package Offer.offer2019;

import domain.ListNode;

/**
 * O(1)时间删除链表结点
 * @author: leiwenkang02@meituan.com
 * @date: 2019/4/26
 * @time: 15:53
 */
public class Offer13 {
    public void deleteListNode(ListNode head, ListNode deletedNode) {
        if (head == null || deletedNode == null) {
            return;
        }
        //如果要遍历到要删除节点的上一个节点，再去删除，则需要O(n)的时间复杂度了
        //因此我们考虑删除deletedNode的下一个节点，只是把下一个节点的值赋值给deletedNode，
        // 这样就相当于删除了deletedNode
        if (deletedNode.next != null) {
            ListNode next = deletedNode.next;
            //将下一个节点的值赋值给deletedNode
            deletedNode.val = next.val;
            //删除deletedNode的下一个节点
            deletedNode.next = next.next;
        } else if (head == deletedNode) {//链表只有一个头节点
            //删除头结点，这里就直接把head置为空把
            head = null;
        } else {//链表中有多个节点，删除尾节点，只能遍历
            ListNode p = head;
            while (p.next != deletedNode) {
                p = p.next;
            }

            p.next = null;
        }

    }
}
